// https://www.lintcode.com/problem/coin-change/my-submissions

class Solution {
public:
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
     
    // TLE，不要随便输出
    // 背包问题，对每个硬币来取
    // int coinChange(vector<int> &coins, int amount) {
    //     vector<int> result(amount + 1, INT_MAX);
    //     result[0] = 0;
    //     for (int i = 0; i < coins.size(); ++i)
    //     {
    //         for (int j = 0; j <= amount - coins[i]; ++j)
    //         {
    //             if (result[j] != INT_MAX)
    //                 result[j + coins[i]] = min(result[j + coins[i]], result[j] + 1); //注意用INT_MAX加1会越界 要先判断
    //         }
    //     }
    //     return result.back() == INT_MAX ? -1: result.back();
    // }
    
   // 换循环顺序，每一步尝试三种硬币，一共27步
    int coinChange(vector<int> &coins, int amount) {
        vector<int> result(amount + 1, INT_MAX);
        result[0] = 0;
        for (int i = 1; i <= amount; ++i)
        {
            for (int j = 0; j < coins.size(); ++j)
            {
                if (i >= coins[j] && result[i - coins[j]] != INT_MAX)
                {
                    // result[i] = min(result[i], result[i - coins[j]]);
                    result[i] = min(result[i], result[i - coins[j]] + 1); //别忘+1
                }
            }
        }
        if (result.back() == INT_MAX) result.back() = -1;
        return result.back();
    } 
};